{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Paths III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: uniquePathsIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同路径 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在二维网格 <code>grid</code> 上，有 4 种类型的方格：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1</code> 表示起始方格。且只有一个起始方格。</li>\n",
    "\t<li><code>2</code> 表示结束方格，且只有一个结束方格。</li>\n",
    "\t<li><code>0</code> 表示我们可以走过的空方格。</li>\n",
    "\t<li><code>-1</code> 表示我们无法跨越的障碍。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目<strong>。</strong></p>\n",
    "\n",
    "<p><strong>每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们有以下两条路径：\n",
    "1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)\n",
    "2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[1,0,0,0],[0,0,0,0],[0,0,0,2]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>我们有以下四条路径： \n",
    "1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)\n",
    "2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)\n",
    "3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)\n",
    "4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[0,1],[2,0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "没有一条路能完全穿过每一个空的方格一次。\n",
    "请注意，起始和结束方格可以位于网格中的任意位置。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= grid.length * grid[0].length &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-paths-iii](https://leetcode.cn/problems/unique-paths-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-paths-iii](https://leetcode.cn/problems/unique-paths-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]', '[[1,0,0,0],[0,0,0,0],[0,0,0,2]]', '[[0,1],[2,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(x: int, y: int, left: int) -> int:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] < 0:\n",
    "                return 0  # 不合法\n",
    "            if grid[x][y] == 2:  # 到达终点\n",
    "                return left == 0  # 必须访问所有的无障碍方格\n",
    "            grid[x][y] = -1  # 标记成访问过，因为题目要求「不能重复通过同一个方格」\n",
    "            ans = dfs(x - 1, y, left - 1) + dfs(x, y - 1, left - 1) + \\\n",
    "                  dfs(x + 1, y, left - 1) + dfs(x, y + 1, left - 1)\n",
    "            grid[x][y] = 0  # 恢复现场\n",
    "            return ans\n",
    "\n",
    "        cnt0 = sum(row.count(0) for row in grid)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 1:  # 起点\n",
    "                    return dfs(i, j, cnt0 + 1)  # +1 把起点也算上\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(flag, x, y, cnt):\n",
    "            ans = 0\n",
    "            if 0<=x<m and 0<=y<n and not flag[x][y] and grid[x][y]>=0:\n",
    "                if grid[x][y] == 2:\n",
    "                    return 1 if cnt == mcnt else 0\n",
    "                flag[x][y] = True\n",
    "                for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                    ans += dfs(flag, x+i, y+j, cnt+1)\n",
    "                flag[x][y] = False\n",
    "            return ans\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        flag = [[False]*n for i in range(m)]\n",
    "        bi, bj, mcnt = -1, -1, 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    bi, bj = i, j\n",
    "                if grid[i][j] != -1:\n",
    "                    mcnt += 1\n",
    "        return dfs(flag, bi, bj, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, n = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 0:\n",
    "                    n += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    n += 1\n",
    "                    si, sj = i, j\n",
    "        def dfs(i, j, n):\n",
    "            if grid[i][j] == 2:\n",
    "                if n == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            t = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                nx, ny = i + dx, j + dy\n",
    "                if 0 <= nx < r and 0 <= ny < c and grid[nx][ny] in [0, 2]:\n",
    "                    res += dfs(nx, ny, n - 1)\n",
    "            grid[i][j] = t\n",
    "            return res\n",
    "        return dfs(si, sj, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        si = sj = cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    cnt += 1\n",
    "                if grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "                    cnt += 1\n",
    "        dirs = [0, 1, 0, -1, 0]\n",
    "        def dfs(i: int, j: int, count):\n",
    "            if grid[i][j] == 2:\n",
    "                if count == cnt:\n",
    "                    return 1\n",
    "                return 0\n",
    "            t = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0\n",
    "            for k in range(4):\n",
    "                dx, dy = i + dirs[k], j + dirs[k + 1]\n",
    "                if 0 <= dx < m and 0 <= dy < n and grid[dx][dy] in [0, 2]:\n",
    "                    res += dfs(dx, dy, count + 1)\n",
    "            grid[i][j] = t\n",
    "            return res\n",
    "        return dfs(si, sj, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i: int, j: int, k: int) -> int:\n",
    "            if grid[i][j] == 2:\n",
    "                return int(k == cnt + 1)\n",
    "            ans = 0\n",
    "            for a, b in pairwise(dirs):\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in vis and grid[x][y] != -1:\n",
    "                    vis.add((x, y))\n",
    "                    ans += dfs(x, y, k + 1)\n",
    "                    vis.remove((x, y))\n",
    "            return ans\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        start = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == 1)\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        cnt = sum(row.count(0) for row in grid)\n",
    "        vis = {start}\n",
    "        return dfs(*start, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, n = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 0:\n",
    "                    n += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    n += 1\n",
    "                    si, sj = i, j\n",
    "\n",
    "        def dfs(i: int, j: int, n: int) -> int:\n",
    "            if grid[i][j] == 2:\n",
    "                if n == 0:return 1\n",
    "                return 0\n",
    "            t = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0\n",
    "            for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < r and 0 <= nj < c and grid[ni][nj] in [0, 2]:\n",
    "                    res += dfs(ni, nj, n - 1)\n",
    "            grid[i][j] = t\n",
    "            return res\n",
    "\n",
    "        return dfs(si, sj, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        result = [0]\n",
    "        total = 0\n",
    "        start_x, start_y = -1, -1\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    total += 1\n",
    "                if grid[i][j] == 1:\n",
    "                    start_x, start_y = i, j\n",
    "        \n",
    "        def dfs(now_points, now_x, now_y):\n",
    "            x = [-1, 0, 1, 0, -1]\n",
    "            for m in range(4):\n",
    "                next_x, next_y = now_x + x[m], now_y + x[m+1]\n",
    "                if 0 <= next_x < len(grid) and 0 <= next_y < len(grid[0]):\n",
    "                    if grid[next_x][next_y] == 2:\n",
    "                        if now_points == total:\n",
    "                            result[0] += 1\n",
    "                            return\n",
    "                    elif grid[next_x][next_y] == 0:\n",
    "                        grid[next_x][next_y] = 1\n",
    "                        dfs(now_points + 1, next_x, next_y)\n",
    "                        grid[next_x][next_y] = 0\n",
    "\n",
    "        dfs(0, start_x, start_y)\n",
    "        return result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        rows, columns = len(grid), len(grid[0])\n",
    "        direction_list = [[1, 0], [0, -1], [-1, 0], [0, 1]]\n",
    "        start_x, start_y, target = initialize(grid, rows, columns)\n",
    "        return dfs(grid, rows, columns, target, direction_list, start_x, start_y)\n",
    "def initialize(grid, rows, columns):\n",
    "    target = 0\n",
    "    for row in range(rows):\n",
    "        for column in range(columns):\n",
    "            if grid[row][column] == 1:\n",
    "                start_x = row \n",
    "                start_y = column\n",
    "            elif grid[row][column] == 0:\n",
    "                target += 1\n",
    "    return [start_x, start_y, target]\n",
    "\n",
    "def dfs(grid, rows, columns, target, direction_list, start_x, start_y):\n",
    "    if start_x < 0 or start_x >= rows or start_y < 0 or start_y >= columns:\n",
    "        return 0\n",
    "    if grid[start_x][start_y] == -1:\n",
    "        return 0\n",
    "    if grid[start_x][start_y] == 2:\n",
    "        if target:\n",
    "            return 0 \n",
    "        else:\n",
    "            return 1\n",
    "    path_sum = 0\n",
    "    if grid[start_x][start_y] == 1:\n",
    "        grid[start_x][start_y] = -1\n",
    "        for direction in direction_list:\n",
    "            path_sum +=  dfs(grid, rows, columns, target, direction_list, start_x + direction[0], start_y + direction[1])\n",
    "    else:\n",
    "        grid[start_x][start_y] = -1\n",
    "        for direction in direction_list:\n",
    "            path_sum +=  dfs(grid, rows, columns, target - 1, direction_list, start_x + direction[0], start_y + direction[1])\n",
    "        grid[start_x][start_y] = 0\n",
    "\n",
    "    return path_sum\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, n = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 0:\n",
    "                    n += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    n += 1\n",
    "                    si, sj = i, j\n",
    "\n",
    "        def dfs(i: int, j: int, n: int) -> int:\n",
    "            if grid[i][j] == 2:\n",
    "                if n == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            t = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0\n",
    "            for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < r and 0 <= nj < c and grid[ni][nj] in [0, 2]:\n",
    "                    res += dfs(ni, nj, n - 1)\n",
    "            grid[i][j] = t\n",
    "            return res\n",
    "\n",
    "        return dfs(si, sj, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0:\n",
    "                    cnt += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    cnt += 1\n",
    "                    si, sj = i, j\n",
    "\n",
    "\n",
    "        def dfs(i: int, j: int, cnt: int) -> int:\n",
    "            if grid[i][j] == 2:\n",
    "                if cnt == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            t = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0\n",
    "            for di, dj in dirs:\n",
    "                ni = i + di\n",
    "                nj = j + dj\n",
    "                if ni >= 0 and ni < n and nj >= 0 and nj < m and grid[ni][nj] in [0, 2]:\n",
    "                    res += dfs(ni, nj, cnt-1)\n",
    "            grid[i][j] = t\n",
    "            return res\n",
    "\n",
    "        res = dfs(si, sj, cnt)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        # find StartPoint and get num of 0: n\n",
    "        # use built-in : list[nested]\n",
    "        # for _ in range(): \n",
    "        # 回溯!!!\n",
    "        r,c = len(grid),len(grid[0])\n",
    "        n = 0\n",
    "        si,sj = 0,0 # start i,j\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 0:\n",
    "                    n += 1\n",
    "                if grid[i][j] == 1:\n",
    "                    n += 1\n",
    "                    si = i\n",
    "                    sj = j\n",
    "                \n",
    "        def dfs(i:int,j:int,n:int)->int:\n",
    "           # i, j default are in range   \n",
    "            if grid[i][j] == 2: # reach ending\n",
    "                if n == 0:\n",
    "                    return 1 # success\n",
    "                return 0 # Fail\n",
    "        # =======================没到终点 ======================\n",
    "          #先将脚下标记为-1，即进入递归(子情况)时，此处视为障碍物\n",
    "            temp = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0 # 默认返回值 \n",
    "            direct = [[1,0],[0,1],[-1,0],[0,-1]]\n",
    "            for di,dj in direct:\n",
    "                ni = i + di \n",
    "                nj = j + dj\n",
    "              # 往四个正方向扩展时，需要判断边界, 以及障碍物 !!! \n",
    "                if 0<=ni<r and 0<=nj<c and grid[ni][nj] in [0,2]: \n",
    "                    res += dfs(ni,nj, n-1)\n",
    "          # 遍历完了所有子路径，res加上了\"所有子路径\"条数: 可行res+= 1，不行res+= 0.     \n",
    "            grid[i][j] = temp #恢复地图原貌，其实可以不恢复???\n",
    "            return res\n",
    "\n",
    "        return dfs(si,sj,n)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def backtrack(si, sj):\n",
    "\n",
    "            if len(path) == max_walkable and grid[si][sj] == 2:\n",
    "                result.append(path.copy())\n",
    "                return\n",
    "\n",
    "            for dx, dy in options:\n",
    "                new_x, new_y = si + dx, sj + dy\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] != -1:\n",
    "                    if (new_x, new_y) in visited:\n",
    "                        continue\n",
    "\n",
    "                    visited.add((new_x, new_y))\n",
    "                    path.append((new_x, new_y))\n",
    "                    backtrack(new_x, new_y)\n",
    "                    path.pop()\n",
    "                    visited.remove((new_x, new_y))\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        max_walkable = 0\n",
    "        options = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        visited = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "                if grid[i][j] != -1:\n",
    "                    max_walkable += 1\n",
    "\n",
    "        visited.add((si,sj))\n",
    "        path = [(si, sj)]\n",
    "        result = []\n",
    "\n",
    "        backtrack(si, sj)\n",
    "\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        for x in grid:\n",
    "            print(x)\n",
    "        for i, x in enumerate(grid):\n",
    "            for j, val in enumerate(x):\n",
    "                if val == 0:\n",
    "                    cnt += 1\n",
    "                if val == 1:\n",
    "                    st = [i, j]\n",
    "                if val == 2:\n",
    "                    ed = [i, j]\n",
    "        def dfs(i: int, j: int,cnt: int) -> int:\n",
    "            #boundary:\n",
    "            if i < 0 or i == m or j == n or j < 0 or grid[i][j] == -1:\n",
    "                return 0\n",
    "            if i == st[0] and j == st[1]:\n",
    "                return 1 if cnt == 0 else 0\n",
    "            #val_return\n",
    "            #where\n",
    "            #枚举向哪走\n",
    "            grid[i][j] = -1\n",
    "            path.append(grid[i][j])\n",
    "            res = dfs(i, j - 1, cnt - 1) + dfs(i - 1, j, cnt - 1) + dfs(i, j + 1, cnt - 1) + dfs(i + 1, j, cnt - 1)\n",
    "            grid[i][j] = 0\n",
    "            return res\n",
    "        \n",
    "        return dfs(ed[0], ed[1], cnt + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        si,sj,st = 0,0,0\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] in [0,2]:\n",
    "                    st |= (1 << (i*c+j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    si,sj = i, j \n",
    "        \n",
    "        @lru_cache \n",
    "        def dp(i, j, t):\n",
    "            if grid[i][j] == 2:\n",
    "                if t == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0 \n",
    "            res = 0\n",
    "            for [di,dj] in [[0,1], [1, 0], [0, -1], [-1,0]]:\n",
    "                ni, nj = i+di, j+dj\n",
    "                if 0<=ni < r and 0<=nj<c and t & (1 << (ni*c+nj)):\n",
    "                    res += dp(ni,nj, t^(1<<(ni*c+nj)))\n",
    "\n",
    "            return res \n",
    "        return dp(si,sj, st) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # 1000\n",
    "        # 0000\n",
    "        # 002-\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        all_used_grid = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    startx, starty = i, j\n",
    "                elif grid[i][j] == 2:\n",
    "                    endx, endy = i, j \n",
    "                elif grid[i][j] == 0:\n",
    "                    all_used_grid += 1\n",
    "        # print(startx,starty, endx, endy, all_used_grid)\n",
    "        # self.res = 0\n",
    "        self.sum = 0\n",
    "        # visit = set()\n",
    "\n",
    "\n",
    "        # @cache不能直接用cache：\n",
    "        # 理解!!!就比如说到达了1个点前面left一样，有个分叉路口，他们后面的路径可能不一样，后面的路径不一样那返回的dfs值肯定不一样，因为前面遍历过的会被置为-1。\n",
    "        # 那如果其中一条路到不了会导致dfs记忆返回0，那另一条如果能到达也会被误认为返回0\n",
    "        self.path = []\n",
    "        # @cache\n",
    "        def dfs(x, y, left):\n",
    "\n",
    "            if x==endx and y==endy:\n",
    "                if left+1==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    # print(666)\n",
    "                    # print(self.path)\n",
    "                    return 0\n",
    "            \n",
    "            tsum = 0\n",
    "            \n",
    "            for tx,ty in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                if 0<=tx<m and 0<=ty<n and grid[tx][ty] != -1:\n",
    "                    temp = grid[tx][ty]\n",
    "                    grid[tx][ty] = -1\n",
    "                    self.path.append((tx,ty))\n",
    "                    tsum += dfs(tx, ty, left-1)\n",
    "                    self.path.pop()\n",
    "\n",
    "                    grid[tx][ty] = temp\n",
    "            \n",
    "            print(x,y,left,tsum)\n",
    "            return tsum\n",
    "\n",
    "\n",
    "        grid[startx][starty] = -1\n",
    "        \n",
    "        return dfs(startx, starty, left=all_used_grid)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,grid,res,i,j,path,target):\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if i<0 or i>=m or j<0 or j>=n: return res\n",
    "        \n",
    "        if grid[i][j] == 2:\n",
    "            res.append(path)\n",
    "            return res\n",
    "        elif grid[i][j] == -1 : \n",
    "            return res\n",
    "        else:\n",
    "            for (mx,my) in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:\n",
    "                grid[i][j] = -1\n",
    "                res = self.dfs(grid,res,mx,my,path + [(i,j)],target)\n",
    "                grid[i][j] = 0\n",
    "        return res\n",
    "                    \n",
    "                    \n",
    "    def uniquePathsIII(self, grid):\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        target = 1\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 0: target+=1\n",
    "                    \n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1: res = self.dfs(grid,[],x,y,[],target)\n",
    "        \n",
    "        right = 0\n",
    "        for item in res:\n",
    "            if len(item) == target: right += 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: list[list[int]]) -> int:\n",
    "        N = 30\n",
    "        # 下右上左\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        # 记录路径条数\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i, j, cnt):\n",
    "            nonlocal res\n",
    "            # 标记(i,j)已经访问过【0变为-1】\n",
    "            if grid[i][j]==0:\n",
    "                grid[i][j] = -1\n",
    "                cnt -= 1\n",
    "            print(i,j,cnt)\n",
    "\n",
    "            for dir in directions:\n",
    "                x, y = i + dir[0], j + dir[1]\n",
    "                if 0 <= x < len(grid) and 0 <= y < len(grid[0]):\n",
    "                    if grid[x][y] == 0:\n",
    "                        dfs(x, y, cnt)\n",
    "                        # 回溯，(x,y)恢复为未访问\n",
    "                        grid[x][y] = 0\n",
    "                    elif grid[x][y] == 2:\n",
    "                        # 表示到了终点\n",
    "                        if cnt == 0:\n",
    "                            # 且所有0已经被遍历完了\n",
    "                            res += 1\n",
    "                            return\n",
    "                        else:\n",
    "                            continue\n",
    "\n",
    "        # 求0的个数\n",
    "        cnt = sum((map(lambda x: x.count(0), grid)))\n",
    "        # 找起点\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        cnt0=0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        x,y=0,0\n",
    "        rds=[(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==2:\n",
    "                    x,y=i,j\n",
    "                if grid[i][j]==0:\n",
    "                    cnt0+=1 \n",
    "        def dfs(i,j,ct,vis):\n",
    "            if i<0 or i>=m:return 0\n",
    "            if j<0 or j>=n:return 0\n",
    "            print(i,j,ct)\n",
    "            if grid[i][j]==-1:\n",
    "                return 0\n",
    "            if grid[i][j]==1:\n",
    "                if ct==0:\n",
    "                    return 1\n",
    "                else: return 0\n",
    "            \n",
    "            if grid[i][j]==0  and ct==0:\n",
    "                return 0\n",
    "            res=0\n",
    "            for rx,ry in rds:\n",
    "                nx,ny=i+rx,j+ry\n",
    "                if 0<=nx<m and 0<=ny<n and  (nx,ny) not in vis:\n",
    "             \n",
    "                    vis.add((nx,ny))\n",
    "                    res+=dfs(nx,ny,ct-1,vis)\n",
    "                    vis.remove((nx,ny))\n",
    "            return res\n",
    "        vs=set()\n",
    "        vs.add((x,y))\n",
    "        # print(x,y)\n",
    "        return dfs(x,y,cnt0+1,vs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        start, end = None, None\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        zero_num = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    start = [i, j]\n",
    "                if grid[i][j] == 0:\n",
    "                    zero_num += 1\n",
    "        queue = [[start]]\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        count = 0\n",
    "        while queue:\n",
    "            path = queue.pop(0)\n",
    "            # print(path)\n",
    "            x, y = path[-1]\n",
    "            for dx, dy in direction:\n",
    "                newx = x + dx\n",
    "                newy = y + dy\n",
    "                if 0 <= newx < m and 0 <= newy < n and [newx, newy] not in path:\n",
    "                    if grid[newx][newy] == 2 and len(path) == zero_num+1:\n",
    "                        # print(path)\n",
    "                        count += 1\n",
    "                    elif grid[newx][newy] == 0:\n",
    "                        queue.append(path+[[newx, newy]])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "#         m, n = len(grid), len(grid[0])\n",
    "#         todo = 0\n",
    "#         for i, x in enumerate(grid):\n",
    "#             for j, val in enumerate(x):\n",
    "#                 if not val & 1:\n",
    "#                     todo |= 1 << (i * n + j)\n",
    "#                 if val == 1:\n",
    "#                     si, sj = i, j\n",
    "#                 if val == 2:\n",
    "#                     ti, tj = i, j\n",
    "\n",
    "#         @cache\n",
    "#         def bt(i, j, todo):\n",
    "#             return 1 if i == ti and j == tj and not todo else sum(\n",
    "#                 bt(x, y, todo ^ mask)\n",
    "#                 for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))\n",
    "#                 if 0 <= x < m and 0 <= y < n and (mask := 1 << (x * n + y)) & todo\n",
    "#             )\n",
    "#         return bt(si, sj, todo)\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def code(r, c):\n",
    "            return 1 << (r * C + c)\n",
    "\n",
    "        def neibbbors(r, c):\n",
    "            for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):\n",
    "                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:\n",
    "                    yield nr, nc\n",
    "\n",
    "        target = 0\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, val in enumerate(row):\n",
    "                if val % 2 == 0:\n",
    "                    target |= code(r, c)\n",
    "\n",
    "                if val == 1:\n",
    "                    sr, sc = r, c\n",
    "                if val == 2:\n",
    "                    tr, tc = r, c\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(r, c, todo):\n",
    "            if r == tr and c == tc:\n",
    "                return +(todo == 0)\n",
    "\n",
    "            ans = 0\n",
    "            for nr, nc in neibbbors(r, c):\n",
    "                if todo & code(nr, nc):\n",
    "                    ans += dp(nr, nc, todo ^ code(nr, nc))\n",
    "            return ans\n",
    "\n",
    "        return dp(sr, sc, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def bfs(self,x,y,path):\n",
    "        for dx, dy in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "            x1, y1 = x + dx, y + dy\n",
    "            if x1 in range(self.m) and y1 in range(self.n) and (x1,y1) not in path:\n",
    "                path1 = path + [(x1,y1)]\n",
    "                if self.grid[x1][y1] == 0:\n",
    "                    self.bfs(x1,y1,path1)\n",
    "                elif self.grid[x1][y1] == 2:\n",
    "                    self.paths.add(tuple(path1))\n",
    "\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(grid), len(grid[0])\n",
    "        self.grid = grid\n",
    "        self.paths = set([])\n",
    "        s = sum([sum([1 if y in [1,0,2] else 0 for y in x]) for x in grid])\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.bfs(i,j,[(i,j)])\n",
    "                    break\n",
    "        ans = 0\n",
    "        for each in self.paths:\n",
    "            if len(each) == s:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nearby = defaultdict(list)\n",
    "        directions = [(0, 1), (1, 0)]\n",
    "        dest = -1\n",
    "        start = -1\n",
    "        cnt = 0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == -1:\n",
    "                    continue\n",
    "                left = x*n+y\n",
    "                cnt += 1\n",
    "                for d in directions:\n",
    "                    new_x, new_y = x+d[0], y+d[1]\n",
    "                    if new_x < 0 or new_x == m or new_y < 0 or new_y == n or grid[new_x][new_y] == -1:\n",
    "                        continue\n",
    "                    right = new_x*n+new_y\n",
    "                    nearby[left].append(right)\n",
    "                    nearby[right].append(left)\n",
    "                if grid[x][y] == 1:\n",
    "                    start = left\n",
    "                elif grid[x][y] == 2:\n",
    "                    dest = left\n",
    "                else:\n",
    "                    pass\n",
    "        cnt -= 1\n",
    "\n",
    "        ret = 0\n",
    "        q = [[list(), start]]\n",
    "        while q:\n",
    "            new_q = list()\n",
    "            for passed, pos in q:\n",
    "                if pos == dest:\n",
    "                    if len(passed) == cnt:\n",
    "                        ret += 1\n",
    "                else:\n",
    "                    for nxt in nearby[pos]:\n",
    "                        if nxt in passed:\n",
    "                            continue\n",
    "                        new_q.append([passed+[pos], nxt])\n",
    "            q = new_q\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        c = 0\n",
    "        pass_point = set()\n",
    "        cannot_point = set()\n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    c += 1\n",
    "                    pass_point.add((i,j))\n",
    "                elif grid[i][j] == -1:\n",
    "                    cannot_point.add((i,j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    start_point = (i,j)\n",
    "                else:\n",
    "                    end_point = (i,j)\n",
    "\n",
    "        now_road = [[start_point]]\n",
    "        next_road = []\n",
    "        for nn in range(c+1):\n",
    "            while now_road != []:\n",
    "                this_road = now_road.pop()\n",
    "                i,j = this_road[-1]\n",
    "\n",
    "                for i0,j0 in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):\n",
    "                    if i0<0 or i0==m or j0 < 0 or j0 == n:\n",
    "                        continue\n",
    "                    elif (i0,j0) in this_road or (i0,j0) in cannot_point:\n",
    "                        continue\n",
    "                    elif (i0,j0) == end_point:\n",
    "                        if nn < c:\n",
    "                            continue\n",
    "                        else:\n",
    "                            result += 1\n",
    "                    else:\n",
    "                        ls = this_road[:]\n",
    "                        ls.append((i0,j0))\n",
    "                        next_road.append(ls)\n",
    "            \n",
    "            now_road = next_road[:]\n",
    "            next_road = [] \n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def code(r, c):\n",
    "            return 1 << (r * C + c)\n",
    "\n",
    "        def neighbors(r, c):\n",
    "            for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):\n",
    "                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:\n",
    "                    yield nr, nc\n",
    "\n",
    "        target = 0\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, val in enumerate(row):\n",
    "                if val % 2 == 0:\n",
    "                    target |= code(r, c)\n",
    "\n",
    "                if val == 1:\n",
    "                    sr, sc = r, c\n",
    "                if val == 2:\n",
    "                    tr, tc = r, c\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(r, c, todo):\n",
    "            if r == tr and c == tc:\n",
    "                return +(todo == 0)\n",
    "\n",
    "            ans = 0\n",
    "            for nr, nc in neighbors(r, c):\n",
    "                if todo & code(nr, nc):\n",
    "                    ans += dp(nr, nc, todo ^ code(nr, nc))\n",
    "            return ans\n",
    "\n",
    "        return dp(sr, sc, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # dp[i][j]中是一个字典。dp[i][j][state]的意思是，在state的情况下，从(i,j)这个空地出发，得到的路线数目。\n",
    "        dp = [[{} for _ in range(n)] for _ in range(m)]\n",
    "        # 计算空地数目\n",
    "        space_cnt = 0  # 空地数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    space_cnt += 1\n",
    "        # 构造起始状态。状态是把每个格子作为1个二进制布尔值，1表示堵塞，0表示通透。\n",
    "        state = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == -1:\n",
    "                    state |= 1 << (i * n + j)\n",
    "\n",
    "        def dfs(i, j):\n",
    "            nonlocal state, space_cnt\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == -1:  # 非法情况\n",
    "                return 0\n",
    "            if grid[i][j] == 2:  # 到达目标位置\n",
    "                if space_cnt != 1:\n",
    "                    return 0\n",
    "                return 1\n",
    "            if state in dp[i][j]:\n",
    "                return dp[i][j][state]\n",
    "            # 落地\n",
    "            pos = i * n + j\n",
    "            state |= 1 << pos\n",
    "            grid[i][j] = -1\n",
    "            space_cnt -= 1\n",
    "            ans = dfs(i, j - 1) + dfs(i, j + 1) + dfs(i - 1, j) + dfs(i + 1, j)\n",
    "            # 回溯\n",
    "            space_cnt += 1\n",
    "            grid[i][j] = 0\n",
    "            state &= ~(1 << pos)\n",
    "            dp[i][j][state] = ans\n",
    "            return ans\n",
    "\n",
    "        # 找到起始位置\n",
    "        i0 = j0 = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    i0 = i\n",
    "                    j0 = j\n",
    "                    break\n",
    "        return dfs(i0, j0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        def get_all_new_positions(my_path):\n",
    "            nonlocal m\n",
    "            nonlocal n\n",
    "            nonlocal grid\n",
    "            x, y = my_path[-1][0], my_path[-1][1]\n",
    "            return [p for p in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)] if 0<=p[0]<m and 0<=p[1]<n and grid[p[0]][p[1]]!=-1 and p not in my_path]\n",
    "\n",
    "        m, n, n_steps = len(grid), len(grid[0]), 0\n",
    "        s, e = None, None\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 1 and grid[i][j] != -1:\n",
    "                    n_steps += 1\n",
    "                if grid[i][j] == 1:\n",
    "                    s = (i, j)\n",
    "                elif grid[i][j] == 2:\n",
    "                    e = (i, j)\n",
    "        old_paths = [[s]]\n",
    "        for t in range(n_steps):\n",
    "            new_paths = []\n",
    "            for path in old_paths:\n",
    "                if path[-1] == e:\n",
    "                    continue\n",
    "                all_new_positions = get_all_new_positions(path)\n",
    "                for new_pos in all_new_positions:\n",
    "                    new_paths.append(path+[new_pos])\n",
    "            old_paths = new_paths\n",
    "        return len(old_paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        def get_all_new_positions(my_path):\n",
    "            nonlocal m\n",
    "            nonlocal n\n",
    "            nonlocal grid\n",
    "            x, y = my_path[-1][0], my_path[-1][1]\n",
    "            if grid[x][y] == 2:\n",
    "                return []\n",
    "            return [p for p in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)] if 0<=p[0]<m and 0<=p[1]<n and grid[p[0]][p[1]]!=-1 and p not in my_path]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        n_steps = m * n - 1\n",
    "        start_point = None\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == -1:\n",
    "                    n_steps -= 1\n",
    "                if grid[i][j] == 1:\n",
    "                    start_point = (i, j)\n",
    "        old_paths = [[start_point]]\n",
    "        for t in range(n_steps):\n",
    "            new_paths = []\n",
    "            for path in old_paths:\n",
    "                all_new_positions = get_all_new_positions(path)\n",
    "                for new_pos in all_new_positions:\n",
    "                    new_paths.append(path+[new_pos])\n",
    "            old_paths = new_paths\n",
    "        return len(old_paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def contain_all_white(self,path,whites):\n",
    "        for x in whites:\n",
    "            if x not in path:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        queue=collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    queue.append([(i,j)])\n",
    "                    break\n",
    "\n",
    "        whites=[(i,j) for i in range(m) for j in range(n) if grid[i][j]==0]\n",
    "        num=0\n",
    "        ans=[]\n",
    "        while queue:\n",
    "            path=queue.popleft()\n",
    "            i,j=path[-1]\n",
    "            if grid[i][j]==2 and self.contain_all_white(path,whites):\n",
    "                num+=1\n",
    "                ans.append(path)\n",
    "            else:\n",
    "                for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    if 0<=x<m and 0<=y<n and grid[x][y] in [0,2] and (x,y) not in path:\n",
    "                        newpath=path+[(x,y)]\n",
    "                        queue.append(newpath)\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        todo = 0\n",
    "        for i, x in enumerate(grid):\n",
    "            for j, val in enumerate(x):\n",
    "                if not val & 1:\n",
    "                    todo |= 1 << (i * n + j)\n",
    "                if val == 1:\n",
    "                    si, sj = i, j\n",
    "                if val == 2:\n",
    "                    ti, tj = i, j\n",
    "\n",
    "        @cache\n",
    "        def bt(i, j, todo):\n",
    "            return 1 if i == ti and j == tj and not todo else sum(\n",
    "                bt(x, y, todo ^ mask)\n",
    "                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))\n",
    "                if 0 <= x < m and 0 <= y < n and not grid[x][y] & 1 and (mask := 1 << (x * n + y)) & todo\n",
    "            )\n",
    "        return bt(si, sj, todo)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    next_move = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        row_len = len(grid)\n",
    "        column_len = len(grid[0])\n",
    "        start,end = None,None\n",
    "        move_count = 0\n",
    "        for row_index in range(row_len):\n",
    "            for column_index in range(column_len):\n",
    "                now_val = grid[row_index][column_index]\n",
    "                if now_val == 1:\n",
    "                    start = (row_index,column_index)\n",
    "                elif now_val ==2:\n",
    "                    end = (row_index,column_index)\n",
    "                elif now_val ==0:\n",
    "                    move_count+=1\n",
    "        result = 0\n",
    "        to_search = deque([(start,set())])\n",
    "        while to_search:\n",
    "            #print(to_search)\n",
    "            position,searched = to_search.popleft()\n",
    "            if position == end:\n",
    "                #print(searched)\n",
    "                if len(searched) == move_count+1:\n",
    "                    result+=1\n",
    "                continue\n",
    "            now_row,now_column = position\n",
    "            for each in Solution.next_move:\n",
    "                new_row = now_row + each[0]\n",
    "                new_column = now_column + each[1]\n",
    "                if new_row >=0 and new_row < row_len and new_column>=0 and new_column < column_len \\\n",
    "                        and (new_row,new_column) not in searched and grid[new_row][new_column]!=-1:\n",
    "                    new_searched = set(each for each in searched)\n",
    "                    new_searched.add((now_row,now_column))\n",
    "                    to_search.append(((new_row,new_column),new_searched))\n",
    "        #print(result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        todo = 0\n",
    "        for i, x in enumerate(grid):\n",
    "            for j, val in enumerate(x):\n",
    "                if not val & 1:\n",
    "                    todo |= 1 << (i * n + j)\n",
    "                if val == 1:\n",
    "                    si, sj = i, j\n",
    "                if val == 2:\n",
    "                    ti, tj = i, j\n",
    "\n",
    "        @cache\n",
    "        def bt(i, j, todo):\n",
    "            return 1 if i == ti and j == tj and not todo else sum(\n",
    "                bt(x, y, todo ^ mask)\n",
    "                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))\n",
    "                if 0 <= x < m and 0 <= y < n and (mask := 1 << (x * n + y)) & todo\n",
    "            )\n",
    "        return bt(si, sj, todo)\n",
    "\n",
    "\n",
    "# from functools import lru_cache\n",
    "# class Solution:\n",
    "#     def uniquePathsIII(self, grid):\n",
    "#         R, C = len(grid), len(grid[0])\n",
    "\n",
    "#         def code(r, c):\n",
    "#             return 1 << (r * C + c)\n",
    "\n",
    "#         def nei***ors(r, c):\n",
    "#             for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):\n",
    "#                 if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:\n",
    "#                     yield nr, nc\n",
    "\n",
    "#         target = 0\n",
    "#         for r, row in enumerate(grid):\n",
    "#             for c, val in enumerate(row):\n",
    "#                 if val % 2 == 0:\n",
    "#                     target |= code(r, c)\n",
    "\n",
    "#                 if val == 1:\n",
    "#                     sr, sc = r, c\n",
    "#                 if val == 2:\n",
    "#                     tr, tc = r, c\n",
    "\n",
    "#         @lru_cache(None)\n",
    "#         def dp(r, c, todo):\n",
    "#             if r == tr and c == tc:\n",
    "#                 return +(todo == 0)\n",
    "\n",
    "#             ans = 0\n",
    "#             for nr, nc in nei***ors(r, c):\n",
    "#                 if todo & code(nr, nc):\n",
    "#                     ans += dp(nr, nc, todo ^ code(nr, nc))\n",
    "#             return ans\n",
    "\n",
    "#         return dp(sr, sc, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dic = {}\n",
    "        idx = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    dic[i, j] = idx\n",
    "                    idx += 1\n",
    "                    if grid[i][j] == 1:\n",
    "                        sx, sy = i, j\n",
    "                    elif grid[i][j] == 2:\n",
    "                        tx, ty = i, j\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, state):\n",
    "            if x == tx and y == ty:\n",
    "                return state.bit_count() == idx\n",
    "            \n",
    "            res = 0\n",
    "            for dx, dy in pairwise(direction):\n",
    "                a, b = x + dx, y + dy\n",
    "                if 0 <= a < m and 0 <= b < n and grid[a][b] != -1 and state & (1 << dic[a, b]) == 0:\n",
    "                    ns = state | (1 << dic[a, b])\n",
    "                    res += dfs(a, b, ns)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(sx, sy, 1 << dic[sx, sy])\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        r0 = 0\n",
    "        c0 = 0\n",
    "        cnt = 0\n",
    "        for r in range(h):\n",
    "            for c in range(w):\n",
    "                if grid[r][c] == 1:\n",
    "                    r0 = r\n",
    "                    c0 = c\n",
    "                if grid[r][c] == 0:\n",
    "                    cnt += 1\n",
    "        ds = ((-1, 0), (0, 1), (1, 0), (0, -1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(r, c, st):\n",
    "            ans = 0\n",
    "            for dr, dc in ds:\n",
    "                rr = r + dr\n",
    "                cc = c + dc\n",
    "                if not (0 <= rr < h and 0 <= cc < w):\n",
    "                    continue\n",
    "                if grid[rr][cc] == 0:\n",
    "                    if not st[rr * w + cc]:\n",
    "                        lst = list(st)\n",
    "                        lst[rr * w + cc] = 1\n",
    "                        ans += dp(r + dr, c + dc, tuple(lst))\n",
    "                if grid[rr][cc] == 2:\n",
    "                    if sum(st) == cnt:\n",
    "                        ans += 1\n",
    "                    \n",
    "            return ans\n",
    "\n",
    "        dpa = dp(r0, c0, tuple([0] * (h * w)))\n",
    "\n",
    "        dp.cache_clear()\n",
    "        return dpa\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBasicInfo(self, grid: List[List[int]]):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        path_block = []\n",
    "        start, end = (), ()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    path_block += [(i, j)]\n",
    "                elif grid[i][j] == 1:\n",
    "                    start = (i, j)\n",
    "                elif grid[i][j] == 2:\n",
    "                    end = (i, j)\n",
    "        return m, n, start, end, set(path_block)\n",
    "    \n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n, start, end, road_block = self.getBasicInfo(grid)\n",
    "        result = 0\n",
    "        bfs_queue = [[start]]\n",
    "        # 检查某路径是否可达\n",
    "        def reachable(routine, i, j):\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if (i, j) not in routine and grid[i][j] != -1:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        while(len(bfs_queue) > 0):\n",
    "            routine = bfs_queue[0]\n",
    "            bfs_queue = bfs_queue[1:]\n",
    "            i, j = routine[-1]\n",
    "            for new_i, new_j in ((i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)):\n",
    "                if reachable(routine, new_i, new_j):\n",
    "                    if grid[new_i][new_j] == 2 and len(road_block - set(routine)) == 0:\n",
    "                        result += 1\n",
    "                    else:\n",
    "                        bfs_queue += [routine + [(new_i, new_j)]]\n",
    "        return result\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        #st = time.time()\n",
    "        \n",
    "        sx, sy, ex, ey = 0, 0, 0, 0\n",
    "        p = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == -1: continue\n",
    "                \n",
    "                if grid[i][j] == 1:\n",
    "                    sx, sy = i, j\n",
    "                if grid[i][j] == 2:\n",
    "                    ex, ey = i, j\n",
    "\n",
    "                p += (1 << (n*i+j))\n",
    "\n",
    "        dq = deque([(1 << (sx*n+sy), sx, sy)])\n",
    "        visit = {}\n",
    "        visit[(1 << (sx*n+sy), sx, sy)] = 1\n",
    "        ve = 1 << (ex*n+ey)\n",
    "        ans = 0\n",
    "        while dq:\n",
    "            v, x, y = dq.popleft()\n",
    "            \n",
    "            if v == p:\n",
    "                ans += visit[(v,x,y)]\n",
    "                continue\n",
    "            \n",
    "            if v & ve > 0: continue\n",
    "            \n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                xx, yy = x+dx, y+dy\n",
    "                if 0 <= xx < m and 0 <= yy < n:\n",
    "                    if grid[xx][yy] == -1: continue\n",
    "                    if v & (1 << (xx*n+yy)) > 0: continue\n",
    "                    vv = v + (1 << (xx*n+yy))\n",
    "                    \n",
    "                    if (vv, xx, yy) not in visit:\n",
    "                        dq.append((vv,xx,yy))\n",
    "                        visit[(vv,xx,yy)]= 0\n",
    "                    \n",
    "                    visit[(vv, xx, yy)] += visit[(v, x, y)]\n",
    "        \n",
    "        #print(time.time()-st) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        endst = 0\n",
    "        for i,gr in enumerate(grid):\n",
    "            for j,g in enumerate(gr):\n",
    "                if g in [0, 1, 2]:\n",
    "                    endst += 1<<(i*n+j)\n",
    "                if g==1:\n",
    "                    si, sj = i, j \n",
    "        \n",
    "        shift = [[-1,0], [1,0], [0,-1], [0,1]]\n",
    "        @cache \n",
    "        def dfs(i, j, st):\n",
    "            st += (1<<(i*n+j))\n",
    "            if grid[i][j]==2:\n",
    "                if st==endst:\n",
    "                    st -= (1<<(i*n+j))\n",
    "                    return 1\n",
    "                else:\n",
    "                    st -= (1<<(i*n+j))\n",
    "                    return 0 \n",
    "            ret = 0\n",
    "            for di, dj in shift:\n",
    "                if 0<=i+di<m and 0<=j+dj<n and grid[i+di][j+dj] in [0,2] and not (1<<((i+di)*n+j+dj))&st:\n",
    "                    ret += dfs(i+di, j+dj, st)\n",
    "            st -= (1<<(i*n+j))\n",
    "            return ret\n",
    "        ans = dfs(si, sj, 0)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        target = 0\n",
    "        start, end = (0, 0), (0, 0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    start = (i, j)\n",
    "                if grid[i][j] == 2:\n",
    "                    end = (i, j)\n",
    "                if grid[i][j] != -1:\n",
    "                    target |= 1 << (i * n + j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask, i, j):\n",
    "            # print(mask,i,j)\n",
    "            mask += 1 << (i * n + j)\n",
    "            if end == (i, j):\n",
    "                return mask == target\n",
    "            ans = 0\n",
    "            for (ni, nj) in [(i + 1, j), (i, j - 1), (i - 1, j), (i, j + 1)]:  # 东南西北 顺时针\n",
    "                if ni < 0 or ni >= m or nj < 0 or nj >= n or grid[ni][nj] not in (0, 2) or mask >> (ni * n + nj) & 1:\n",
    "                    continue\n",
    "                ans += dfs(mask, ni, nj)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, start[0], start[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = 0\n",
    "        dx, dy = [0,0,1,-1], [1,-1,0,0]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, vis):\n",
    "            # print(bin(vis))\n",
    "            vis += 1<<(i*n + j)\n",
    "            if grid[i][j] == 2:\n",
    "                if vis == (1 << (m*n)) - 1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            ans = 0\n",
    "            for k in range(4):\n",
    "                nxti, nxtj = i + dx[k], j + dy[k]\n",
    "                if (nxti >= 0 and nxti<m and nxtj>=0 and nxtj < n) and (grid[nxti][nxtj] %2 == 0 ) and ((vis & (1<<(nxti*n + nxtj))) == 0):\n",
    "                    ans += dfs(nxti, nxtj, vis)\n",
    "            vis -= 1<<(i*n + j)\n",
    "            # print(\"{}, {}, ans: {}\".format(i ,j, ans))\n",
    "            return ans\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    s, t = i, j\n",
    "                if grid[i][j] == -1:\n",
    "                    vis += 1<<(i*n + j)\n",
    "        return dfs(s, t, vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "            r, c = len(grid), len(grid[0])\n",
    "            getIdx = lambda x, y:x * c + y\n",
    "            state = 0\n",
    "            cnt = 0\n",
    "            si, sj = None, None\n",
    "            for i in range(r):\n",
    "                for j in range(c):\n",
    "                    if grid[i][j] in [1,2,0]:\n",
    "                        if grid[i][j] == 1:\n",
    "                            si, sj = i, j\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        state |= 1 << getIdx(i, j)\n",
    "                        \n",
    "            @lru_cache(None)\n",
    "            def dp(i, j, state):\n",
    "                idx = getIdx(i, j)\n",
    "                state |= 1 << idx\n",
    "\n",
    "                if grid[i][j] == 2:\n",
    "                    if state == (1 << (r * c)) - 1:\n",
    "                        return 1\n",
    "                    else:\n",
    "                        return 0\n",
    "\n",
    "\n",
    "                res = 0 \n",
    "                for di, dj in [(1,0),(-1,0),(0,-1),(0,1)]:\n",
    "                    newi, newj = i + di, j + dj\n",
    "                    if 0 <= newi < r and 0 <= newj < c and (1 << getIdx(newi, newj)) & state == 0:\n",
    "                        res += dp(newi, newj, state)\n",
    "\n",
    "                \n",
    "                return res\n",
    "\n",
    "            \n",
    "            return dp(si, sj, state)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans, path = 0, 0\n",
    "        sx, sy = 0, 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] in [0, 2]:\n",
    "                    path |= 1 << (i * n + j)\n",
    "                elif grid[i][j] == 1:\n",
    "                    sx, sy = i, j\n",
    "        @cache\n",
    "        def dfs(x, y, path):\n",
    "            if grid[x][y] == 2:\n",
    "                return path == 0\n",
    "            ans = 0\n",
    "            for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):\n",
    "                if 0 <= nx <= m-1 and 0 <=ny <=n-1 and (path & (1 << (nx * n +ny))):\n",
    "                    ans += dfs(nx, ny, path ^ (1 << (nx * n + ny)))\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return dfs(sx, sy, path)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, st = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] in [0, 2]:\n",
    "                    st |= (1 << (i * c + j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, j: int, st: int) -> int:\n",
    "            if grid[i][j] == 2:\n",
    "                if st == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res = 0\n",
    "            for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < r and 0 <= nj < c and (st & (1 << (ni * c + nj))) > 0:\n",
    "                    res += dp(ni, nj, st ^ (1 << (ni * c + nj)))\n",
    "            return res\n",
    "\n",
    "        return dp(si, sj, st)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, st = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] in [0, 2]:\n",
    "                    st |= (1 << (i * c + j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, j: int, st: int) -> int:\n",
    "            if grid[i][j] == 2:\n",
    "                if st == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res = 0\n",
    "            for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < r and 0 <= nj < c and (st & (1 << (ni * c + nj))) > 0:\n",
    "                    res += dp(ni, nj, st ^ (1 << (ni * c + nj)))\n",
    "            return res\n",
    "\n",
    "        return dp(si, sj, st)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        start_state = 0\n",
    "        start_index = None\n",
    "        end_index = None\n",
    "        next_square = ((0, -1), (-1, 0), (0, 1), (1, 0))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if grid[i][j] == -1:\n",
    "                    start_state |= (1 << index) \n",
    "                elif grid[i][j] == 1:\n",
    "                    start_state |= (1 << index)\n",
    "                    start_index = index\n",
    "                elif grid[i][j] == 2:\n",
    "                    end_index = index\n",
    "\n",
    "        @functools.cache\n",
    "        def backtracking(index: int, state: int) -> int:\n",
    "            if index == end_index:\n",
    "                if state == (1 << m * n) - 1:\n",
    "                    return 1\n",
    "                return 0\n",
    "            current = 0\n",
    "            x, y = index // n, index % n\n",
    "            for i, j in next_square:\n",
    "                if 0 <= x + i < m and 0 <= y + j < n:\n",
    "                    next_index = (x + i) * n + (y + j)\n",
    "                else:\n",
    "                    continue\n",
    "                if state & (1 << next_index):\n",
    "                    continue\n",
    "                current += backtracking(next_index, state | (1 << next_index))\n",
    "            \n",
    "            return current\n",
    "        \n",
    "        return backtracking(start_index, start_state)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        def site_num(i, j):\n",
    "            return i * m + j\n",
    "\n",
    "        finded = 0\n",
    "        si, sj = 0, 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] in [0, 2]:\n",
    "                    finded |= (1 << site_num(i, j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "                \n",
    "        aspect = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y, finded):\n",
    "\n",
    "            if grid[x][y] == 2:\n",
    "                if finded == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for a, b in aspect:\n",
    "                a += x\n",
    "                b += y\n",
    "                if 0 <= a < n and 0 <= b < m and (finded >> site_num(a, b)) & 1:\n",
    "                    ans += dfs(a, b, finded ^ (1 << site_num(a, b)))\n",
    "            return ans\n",
    "\n",
    "        return dfs(si, sj, finded)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n, x, si, sj = len(grid), len(grid[0]), 0, 0, 0\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            if grid[i][j] == 2:\n",
    "                return 1 >> (x > 0)\n",
    "            result = 0\n",
    "            for i1, j1 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0 <= i1 < m and 0 <= j1 < n:\n",
    "                    y = 1 << i1 * n + j1\n",
    "                    result += x & y and dfs(i1, j1, x ^ y)\n",
    "            return result\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "                elif grid[i][j] >= 0:\n",
    "                    x |= 1 << i * n + j\n",
    "        return dfs(si, sj, x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        f = defaultdict(int)\n",
    "        vis = defaultdict(int)\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        target = 0\n",
    "        x,y = 0,0\n",
    "        stat = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x,y = i,j \n",
    "                elif grid[i][j] == -1:\n",
    "                    stat |= (1<<(i*n+j))\n",
    "                if grid[i][j] != 2:\n",
    "                    target |= (1<<(i*n+j))\n",
    "\n",
    "        def dfs(i,j, stat):\n",
    "            if grid[i][j] == 2 and stat==target:\n",
    "                return 1 \n",
    "            elif grid[i][j] == 2:\n",
    "                return 0\n",
    "\n",
    "            if vis[(i,j,stat)]:\n",
    "                return f[(i,j,stat)]\n",
    "            f[(i,j,stat)] = 0\n",
    "            vis[(i,j,stat)] = 1\n",
    "            nxt_stat = stat | (1<<i*n+j) \n",
    "            for di, dj in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                ni,nj = di+i,dj+j\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] != -1:\n",
    "                    if (stat >>(ni*n+nj)) & 1 == 0:\n",
    "                        f[(i,j,stat)] += dfs(ni,nj, nxt_stat)\n",
    "            return f[(i,j,stat)]\n",
    "        \n",
    "        return dfs(x,y,stat)\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, n = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 0:\n",
    "                    n += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    n += 1\n",
    "                    si, sj = i, j\n",
    " \n",
    "        def dfs(i, j, n):\n",
    "            if grid[i][j] == 2:\n",
    "                if n == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            t = grid[i][j]\n",
    "            grid[i][j] = -1\n",
    "            res = 0\n",
    "            for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < r and 0 <= nj < c and grid[ni][nj] in [0, 2]:\n",
    "                    res += dfs(ni, nj, n - 1)\n",
    "            grid[i][j] = t\n",
    "            return res\n",
    "        return dfs(si, sj, n)\n",
    "\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        si, sj, st = 0, 0, 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] in [0, 2]:\n",
    "                    st |= (1 << (i * c + j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    si, sj = i, j\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, st):\n",
    "            if grid[i][j] == 2:\n",
    "                if st == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res = 0\n",
    "            for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < r and 0 <= nj < c and (st & (1 << (ni * c + nj))) > 0:\n",
    "                    res += dp(ni, nj, st ^ (1 << (ni * c + nj)))\n",
    "            return res\n",
    "\n",
    "        return dp(si, sj, st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        print(m, n)\n",
    "        sx, sy, path = 0, 0, 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] in [0, 2]:\n",
    "                    path |= (1 << (i * n + j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    sx, sy = i, j\n",
    "        @cache\n",
    "        def dfs(x, y, path):\n",
    "            if grid[x][y] == 2:\n",
    "                return path == 0\n",
    "            ans = 0\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y-1), (x, y+1)):\n",
    "                print(\"nx, ny:\", nx, ny)\n",
    "                # 不出界且是需要走的路（走过的不考虑，是-1的不考虑）\n",
    "                if 0 <= nx <= m-1 and 0 <= ny <= n-1 and (path & (1 << (nx * n + ny))):\n",
    "                    ans += dfs(nx, ny, path ^ (1 << (nx * n + ny)))\n",
    "            return ans\n",
    "\n",
    "        return dfs(sx, sy, path)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == -1:\n",
    "                    grid[i][j] = 3\n",
    "        g = ''\n",
    "        for i in range(m):\n",
    "            g += ''.join(list(map(lambda x:str(x),grid[i])))\n",
    "        dx = [0,0,1,-1]\n",
    "        dy = [1,-1,0,0]\n",
    "        @lru_cache(None)\n",
    "        def dfs(x:int,y:int,path:str)->int:\n",
    "            if grid[x][y] == 2:\n",
    "                if path.count('0') == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(4):\n",
    "                tx,ty = x + dx[i],y + dy[i]\n",
    "                if tx < 0 or tx >= m or ty < 0 or ty >= n :\n",
    "                    continue\n",
    "                t = tx * n + ty\n",
    "                if path[t] == '2':\n",
    "                    ans += dfs(tx,ty,path)\n",
    "                elif path[t] == '0':\n",
    "                    s = list(path)\n",
    "                    s[t] = '1'\n",
    "                    ans += dfs(tx,ty,''.join(s))\n",
    "\n",
    "            return ans\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = dfs(i,j,g)\n",
    "\n",
    "        return res\n",
    "\n",
    "a = Solution()\n",
    "t = a.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,2,-1]])\n",
    "print(t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid)\n",
    "        l = len(grid[0])\n",
    "        n = 0\n",
    "        sx, sy = 0,0\n",
    "        route = []\n",
    "        for i,r in enumerate(grid):\n",
    "            for j,c in enumerate(r):\n",
    "                if c == 0:\n",
    "                    n+=1\n",
    "                if c == 1:\n",
    "                    sx,sy = i,j\n",
    "\n",
    "\n",
    "        ds = [[0,-1],[-1,0],[1,0],[0,1]]\n",
    "        step = 0\n",
    "\n",
    "        def dfs(i,j):\n",
    "            nonlocal step\n",
    "            nonlocal res\n",
    "            step += 1\n",
    "            tmp = grid[i][j]\n",
    "            route.append((i,j))\n",
    "            #print(route)\n",
    "            if grid[i][j] == 2 and step == n+2:\n",
    "                res += 1\n",
    "                #print(res)\n",
    "            else:\n",
    "                grid[i][j] = -1\n",
    "                for di, dj in ds:\n",
    "                    if di+i<0 or di+i>=m or dj+j<0 or dj+j>=l:\n",
    "                        continue\n",
    "                    if grid[di+i][dj+j] ==-1:\n",
    "                        continue\n",
    "                    dfs(di+i,dj+j)\n",
    "                grid[i][j] = tmp\n",
    "            step -= 1\n",
    "        \n",
    "        dfs(sx,sy)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        N = n * m \n",
    "        end = (1 << N) - 1\n",
    "        start = startP = endP = 0\n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == -1: end ^= 1 << (i * m + j)\n",
    "                elif grid[i][j] == 1: \n",
    "                    startP = i * m + j\n",
    "                    start = 1 << startP \n",
    "                elif grid[i][j] == 2:\n",
    "                    endP = i * m + j\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(stat, p):\n",
    "            if stat == start and p == startP: return 1\n",
    "            res = 0\n",
    "            x, y = p // m, p % m \n",
    "\n",
    "            for i in range(4):\n",
    "                x1 = x + dx[i]\n",
    "                y1 = y + dy[i]\n",
    "                if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m: continue \n",
    "                if grid[x1][y1] == -1: continue \n",
    "                if stat &(1<<(x1 * m + y1)) == 0: continue \n",
    "                res += dfs(stat ^ (1<< p), x1 * m + y1)\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return dfs(end, endP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def find_start_end(grid):\n",
    "            start = (0,0)\n",
    "            end = (0,0)\n",
    "            state = 0\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    idx = i*len(grid[0])+j\n",
    "                    if grid[i][j]==1:\n",
    "                        start = (i,j)\n",
    "                        # state |=(1<<idx)\n",
    "                    elif grid[i][j]==2:\n",
    "                        end = (i,j)\n",
    "                        state |=(1<<idx)\n",
    "                    elif grid[i][j]==0:\n",
    "                        state |=(1<<idx)\n",
    "\n",
    "            return start,end,state\n",
    "        \n",
    "        start,end,state = find_start_end(grid)\n",
    "        # print(state)\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        @cache\n",
    "        def dfs(state,pos):\n",
    "            if pos==end:\n",
    "                # print(state)\n",
    "                return state == 0\n",
    "            result = 0\n",
    "            # print(bin(state),pos)\n",
    "            for d in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                x_,y_ = pos[0]+d[0],pos[1]+d[1]\n",
    "                idx = x_*n+y_\n",
    "                if 0<=x_<m and 0<=y_<n and (grid[x_][y_]==0 or grid[x_][y_]==2) and state&(1<<idx):\n",
    "                    # print(x_,y_)\n",
    "                    result+=dfs(state&~(1<<idx),(x_,y_))\n",
    "            return result\n",
    "\n",
    "        return dfs(state,start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        f = defaultdict(int)\n",
    "        vis = defaultdict(int)\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        target = 0\n",
    "        x,y = 0,0\n",
    "        stat = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x,y = i,j \n",
    "                elif grid[i][j] == -1:\n",
    "                    stat |= (1<<(i*n+j))\n",
    "                if grid[i][j] != 2:\n",
    "                    target |= (1<<(i*n+j))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j, stat):\n",
    "            if grid[i][j] == 2 and stat==target:\n",
    "                return 1 \n",
    "            elif grid[i][j] == 2:\n",
    "                return 0\n",
    "\n",
    "            f[(i,j,stat)] = 0\n",
    "            nxt_stat = stat | (1<<i*n+j) \n",
    "            for di, dj in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                ni,nj = di+i,dj+j\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] != -1:\n",
    "                    if (stat >>(ni*n+nj)) & 1 == 0:\n",
    "                        f[(i,j,stat)] += dfs(ni,nj, nxt_stat)\n",
    "            return f[(i,j,stat)]\n",
    "        \n",
    "        return dfs(x,y,stat)\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        #所有要走过的点\n",
    "        ok = set()\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 1:\n",
    "                    psi, psj = i, j\n",
    "                elif v == 2:\n",
    "                    pei, pej = i, j\n",
    "                elif v == 0:\n",
    "                    ok.add((i, j))\n",
    "\n",
    "        offset = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "\n",
    "        #可以到结束的点\n",
    "        last = set()\n",
    "        for i, j in offset:\n",
    "            i += pei\n",
    "            j += pej\n",
    "\n",
    "            if not ok and i == psi and j == psj:\n",
    "                return 1\n",
    "\n",
    "            if (i, j) in ok:\n",
    "                last.add((i, j))\n",
    "\n",
    "        #所有可能的路径，[已经经过的点，最后一个点坐标]\n",
    "        all = [(set(), psi, psj)]\n",
    "\n",
    "        for _ in range(len(ok)):\n",
    "            now = []\n",
    "            for road, li, lj in all:\n",
    "                for i, j in offset:\n",
    "                    i += li\n",
    "                    j += lj\n",
    "                    if (i, j) in ok and (i, j) not in road:\n",
    "                        _road = road.copy()\n",
    "                        _road.add((i, j))\n",
    "                        now.append((_road, i, j))\n",
    "\n",
    "            all = now\n",
    "\n",
    "        ret = 0\n",
    "        for _, li, lj in all:\n",
    "            if (li, lj) in last:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        flag = 0\n",
    "        target = (1 << (m * n)) - 1\n",
    "        start_x, start_y = 0, 0\n",
    "        val = 1\n",
    "        dp = defaultdict(int)\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                if grid[y][x] == 1:\n",
    "                    flag |= val\n",
    "                    start_x, start_y = x, y\n",
    "                elif grid[y][x] in [-1, 2]:\n",
    "                    flag |= val\n",
    "                val <<= 1\n",
    "\n",
    "        def find(x: int, y: int) -> int:\n",
    "            nonlocal flag\n",
    "            nonlocal target\n",
    "            nonlocal n\n",
    "            if x < 0 or y < 0 or x >= n or y >= m:\n",
    "                return 0\n",
    "            key = f\"{x}_{y}_{flag}\"\n",
    "            if dp[key] == -1:\n",
    "                return 0\n",
    "            elif dp[key] != 0:\n",
    "                return dp[key]\n",
    "            idx = n * y + x\n",
    "            if grid[y][x] == 2:\n",
    "                if flag == target:\n",
    "                    return 1\n",
    "                return 0\n",
    "            elif grid[y][x] == -1 or grid[y][x] == 1:\n",
    "                return 0\n",
    "            if flag >> idx & 1 == 1:\n",
    "                return 0\n",
    "            val = 1 << idx\n",
    "            flag |= val\n",
    "            res = 0\n",
    "            res += find(x + 1, y)\n",
    "            res += find(x - 1, y)\n",
    "            res += find(x, y + 1)\n",
    "            res += find(x, y - 1)\n",
    "            flag &= target - val\n",
    "            if res:\n",
    "                dp[key] = res\n",
    "            else:\n",
    "                dp[key] = -1\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        res += find(start_x + 1, start_y)\n",
    "        res += find(start_x - 1, start_y)\n",
    "        res += find(start_x, start_y + 1)\n",
    "        res += find(start_x, start_y - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        flag = 0\n",
    "        target = (1 << (m * n)) - 1\n",
    "        start_x, start_y = 0, 0\n",
    "        val = 1\n",
    "        dp = defaultdict(int)\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                if grid[y][x] == 1:\n",
    "                    flag |= val\n",
    "                    start_x, start_y = x, y\n",
    "                elif grid[y][x] in [-1, 2]:\n",
    "                    flag |= val\n",
    "                val <<= 1\n",
    "\n",
    "        def find(x: int, y: int) -> int:\n",
    "            nonlocal flag\n",
    "            nonlocal target\n",
    "            nonlocal n\n",
    "            if x < 0 or y < 0 or x >= n or y >= m:\n",
    "                return 0\n",
    "            key = f\"{x}_{y}_{flag}\"\n",
    "            val = dp[key]\n",
    "            if val == -1:\n",
    "                return 0\n",
    "            elif val > 0:\n",
    "                return val\n",
    "            idx = n * y + x\n",
    "            if grid[y][x] == 2:\n",
    "                if flag == target:\n",
    "                    dp[key] = 1\n",
    "                    return 1\n",
    "                dp[key] = -1\n",
    "                return 0\n",
    "            elif grid[y][x] == -1 or grid[y][x] == 1:\n",
    "                dp[key] = -1\n",
    "                return 0\n",
    "            if flag >> idx & 1 == 1:\n",
    "                dp[key] = -1\n",
    "                return 0\n",
    "            val = 1 << idx\n",
    "            flag |= val\n",
    "            res = 0\n",
    "            res += find(x + 1, y)\n",
    "            res += find(x - 1, y)\n",
    "            res += find(x, y + 1)\n",
    "            res += find(x, y - 1)\n",
    "            flag &= target - val\n",
    "            dp[key] = res if res else -1\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        res += find(start_x + 1, start_y)\n",
    "        res += find(start_x - 1, start_y)\n",
    "        res += find(start_x, start_y + 1)\n",
    "        res += find(start_x, start_y - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "\n",
    "        def check(x,y):\n",
    "            return 0<=x<n and 0<=y<m\n",
    "        dx=[-1,1,0,0]\n",
    "        dy=[0,0,-1,1]\n",
    "        last_state=0\n",
    "        begin_state=0\n",
    "        beginx=0\n",
    "        beginy=0\n",
    "        endx=0\n",
    "        endy=0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]!=-1:\n",
    "                    last_state|=1<<(i*m+j)\n",
    "                if grid[i][j]==1:\n",
    "                    beginx=i\n",
    "                    beginy=j\n",
    "                    begin_state|=1<<(i*m+j)\n",
    "                if grid[i][j]==2:\n",
    "                    endx=i\n",
    "                    endy=j\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,y,s):\n",
    "            if x==endx and y==endy and s==last_state:\n",
    "                return 1\n",
    "            res=0\n",
    "            for i in range(4):\n",
    "                nowx=x+dx[i]\n",
    "                nowy=y+dy[i]\n",
    "                if not check(nowx,nowy) or grid[nowx][nowy]==-1:\n",
    "                    continue\n",
    "                if s&(1<<(nowx*m+nowy)):\n",
    "                    continue\n",
    "                res+=dfs(nowx,nowy,s|(1<<(nowx*m+nowy)))\n",
    "            return res\n",
    "        return dfs(beginx,beginy,begin_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        start = [-1, -1]\n",
    "        end = [-1, -1]\n",
    "        state = (1<<(m*n)) - 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                w = grid[i][j]\n",
    "                if w == 1:\n",
    "                    start = [i, j]\n",
    "                elif w == 2:\n",
    "                    end = [i, j]\n",
    "                elif w == -1:\n",
    "                    state ^= (1<<(i*n+j))\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(s, x, y):\n",
    "            if not s:\n",
    "                return 1 if [x, y] == end else 0\n",
    "            res = 0\n",
    "            for a, b in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:\n",
    "                if 0<=a<m and 0<=b<n and s & (1<<(a*n+b)):\n",
    "                    res += dfs(s^(1<<(a*n+b)), a, b)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        a, b = start\n",
    "        state ^= (1<<(a*n+b))\n",
    "        return dfs(state, a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        start = None\n",
    "        end = None\n",
    "        s = \"\"\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    start = (i,j)\n",
    "                    s += \"1\"\n",
    "                elif grid[i][j] == 2:\n",
    "                    end = (i,j)\n",
    "                    s += \"0\"\n",
    "                elif grid[i][j] == -1:\n",
    "                    s += \"1\"\n",
    "                else:\n",
    "                    s += \"0\"\n",
    "        dires = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        @cache\n",
    "        def dfs(s,cur):\n",
    "            if cur == end:\n",
    "                if s == \"1\" * m * n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            ret = 0\n",
    "            for dd in dires:\n",
    "                nx, ny = cur[0] + dd[0], cur[1] + dd[1]\n",
    "                idx = nx * n + ny\n",
    "                if 0<=nx<m and 0<=ny<n and s[idx] =='0':\n",
    "                    s = s[:idx] + '1'+s[idx+1:]\n",
    "                    ret += dfs(s,(nx,ny))\n",
    "                    s = s[:idx] + '0'+s[idx+1:]\n",
    "            return ret\n",
    "        return dfs(s,start)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        start = [-1, -1]\n",
    "        end = [-1, -1]\n",
    "        state = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    start = [i, j]\n",
    "                elif grid[i][j] == 2:\n",
    "                    end = [i, j]\n",
    "                elif grid[i][j] == -1:\n",
    "                    state |= (1<<(i*n+j))\n",
    "        target  = (1<<(m*n)) - 1\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, sta):\n",
    "            if sta == target:\n",
    "                return 1  if x == end[0]*n+end[1] else 0\n",
    "            a, b = x//n, x%n\n",
    "            res = 0\n",
    "            for c, d in [[a+1, b], [a-1, b], [a, b-1], [a, b+1]]:\n",
    "                if 0<=c<m and 0<=d<n and not sta & (1<<(c*n+d)):\n",
    "                    res += dfs(c*n+d, sta | (1<<(c*n+d)))\n",
    "            return res\n",
    "            \n",
    "        return dfs(start[0]*n+start[1], state | (1<<(start[0]*n+start[1])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        M = len(grid[0])\n",
    "\n",
    "        ALL = 0\n",
    "        for i in range(N):\n",
    "            for j in range(M):\n",
    "                if grid[i][j] == 1:\n",
    "                    begin = (i,j)\n",
    "                    ALL |= (1 << (i * M + j))\n",
    "                elif grid[i][j] == 2:\n",
    "                    end = (i,j)\n",
    "                    ALL |= (1 << (i * M + j))\n",
    "                elif grid[i][j] == 0:\n",
    "                    ALL |= (1 << (i * M + j))\n",
    "\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, mask):\n",
    "            #print((i,j))\n",
    "            if mask & (1 << (i * M + j)): # 已经走过了\n",
    "                return 0\n",
    "            mask |= (1 << (i * M + j))\n",
    "\n",
    "            if grid[i][j] == 2:\n",
    "                return int(mask == ALL)\n",
    "            \n",
    "            res = 0\n",
    "            for x, y in [(1,0),(-1,0),(0,-1),(0,1)]:\n",
    "                \n",
    "                if 0 <= i + x and i + x < N and 0 <= j + y and j + y < M and (grid[i+x][j+y]==0 or grid[i+x][j+y]==2):\n",
    "                    res += dfs(i+x, j+y, mask)\n",
    "        \n",
    "            return res\n",
    "        \n",
    "\n",
    "        return dfs(begin[0], begin[1], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        # 回溯 + 记忆化搜索\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x, y, vis = 0, 0, 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x, y = i, j\n",
    "                elif grid[i][j] == -1:\n",
    "                    vis |= 1 << (i * n + j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, vis: int) -> int:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n or vis >> (x * n + y) & 1:\n",
    "                return 0  # 不合法, 分别对应出界和被访问过\n",
    "\n",
    "            vis |= 1 << (x * n + y)\n",
    "            if grid[x][y] == 2:\n",
    "                return vis == (1 << m * n) - 1  # 所有标号都被填完了. 今天才知道true == 1\n",
    "            \n",
    "            return dfs(x - 1, y, vis) + dfs(x, y - 1, vis) + dfs(x + 1, y, vis) + dfs(x, y + 1, vis)\n",
    "\n",
    "        return dfs(x, y, vis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        todo = 0\n",
    "        for i, x in enumerate(grid):\n",
    "            for j, val in enumerate(x):\n",
    "                if not val & 1:\n",
    "                    todo |= 1 << (i * n + j)\n",
    "                if val == 1:\n",
    "                    si, sj = i, j\n",
    "                if val == 2:\n",
    "                    ti, tj = i, j\n",
    "\n",
    "        @cache\n",
    "        def bt(i, j, todo):\n",
    "            return 1 if i == ti and j == tj and not todo else sum(\n",
    "                bt(x, y, todo ^ mask)\n",
    "                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))\n",
    "                if 0 <= x < m and 0 <= y < n and not grid[x][y] & 1 and (mask := 1 << (x * n + y)) & todo\n",
    "            )\n",
    "        return bt(si, sj, todo)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        R = len(grid)\n",
    "        C = len(grid[0])\n",
    "    \n",
    "        All = (1 << R * C) - 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, v):\n",
    "            if i < 0 or i >= R: return 0\n",
    "            if j < 0 or j >= C: return 0\n",
    "            if v >> (i * C + j) & 1: return 0\n",
    "        \n",
    "            v |= 1 << (i * C + j)\n",
    "        \n",
    "            if grid[i][j] == 2:\n",
    "                return All == v\n",
    "            return dfs(i - 1, j, v) + dfs(i + 1, j, v) + dfs(i, j - 1, v) + dfs(i, j + 1, v)\n",
    "    \n",
    "        v = 0\n",
    "    \n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                if grid[i][j] == -1:\n",
    "                      v |= 1 << (i * C + j)\n",
    "                if grid[i][j] == 1:\n",
    "                      sx, sy = i, j\n",
    "        return dfs(sx, sy, v)\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        startx = starty = endx = endy = empty = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    empty |= (1 << (i * n + j))\n",
    "                    if grid[i][j] == 1:\n",
    "                        startx, starty = i, j\n",
    "                    elif grid[i][j] == 2:\n",
    "                        endx, endy = i, j\n",
    "        \n",
    "        @functools.cache\n",
    "        def dp(i, j, visited):\n",
    "            if i == endx and j == endy:\n",
    "                return int(visited == empty)\n",
    "            res = 0\n",
    "            for ii, jj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= ii < m and 0 <= jj < n and (visited >> (ii * n + jj)) & 1 == 0:\n",
    "                    res += dp(ii, jj, visited | (1 << (ii * n + jj)))\n",
    "            return res\n",
    "        return dp(startx, starty, 1 << (startx * n + starty))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "    #     \"\"\"\n",
    "    #     DFS + 回溯\n",
    "    #     \"\"\"\n",
    "    #     def dfs(x, y, left):\n",
    "    #         # 如果越界，则返回0\n",
    "    #         if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] < 0:\n",
    "    #             return 0\n",
    "    #         # 如果遇到2，则表示访问到终点\n",
    "    #         if grid[x][y] == 2:\n",
    "    #             # 判断剩余未访问空方格数是否为0\n",
    "    #             return left == 0\n",
    "    #         grid[x][y] = -1\n",
    "    #         ans = 0\n",
    "    #         for inc_x, inc_y in directions:\n",
    "    #             ans += dfs(inc_x + x, inc_y + y, left - 1)\n",
    "    #         # 回溯（恢复现场）\n",
    "    #         grid[x][y] =0\n",
    "    #         return ans\n",
    "\n",
    "    #     m, n = len(grid), len(grid[0])\n",
    "    #     directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "    #     sum_0 = sum(row.count(0) for row in grid)\n",
    "\n",
    "    #     for i, row in enumerate(grid):\n",
    "    #         for j, v in enumerate(row):\n",
    "    #             if v == 1:  # 起点\n",
    "    #                 return dfs(i, j, sum_0 + 1)  # +1 把起点也算上\n",
    "    \n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        状态压缩（位运算） + 记忆性搜索\n",
    "        把（x，y）映射为 nx+y\n",
    "        \"\"\"\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        # 使用visited 位运算来代替 left\n",
    "        ALL = (1 << m * n ) - 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x, y ,vis:int) -> int:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n or (vis >> (x * n + y) & 1):\n",
    "                return 0\n",
    "            vis |= 1 << ( x * n + y)\n",
    "            if grid[x][y] == 2:\n",
    "                return vis == ALL\n",
    "\n",
    "            # 直接传输 vis作为参数，不共享，所以不需要回溯\n",
    "            return dfs(x, y + 1, vis) + dfs(x, y - 1, vis) + dfs(x - 1, y, vis) + dfs(x + 1, y, vis)\n",
    "\n",
    "        vis = 0\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v < 0:  # 把障碍方格算上\n",
    "                    vis |= 1 << (i * n + j)\n",
    "                elif v == 1:  # 起点\n",
    "                    sx, sy = i, j\n",
    "        return dfs(sx, sy, vis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        start = (0, 0)\n",
    "        end = (0, 0)\n",
    "        block = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = full = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c = grid[i][j]\n",
    "                idx = i * n + j\n",
    "                if c == 1:\n",
    "                    start = (i, j)\n",
    "                elif c == 2:\n",
    "                    end = (i, j)\n",
    "                elif c == -1:\n",
    "                    block.add((i, j))\n",
    "                if c != -1:\n",
    "                    full |= 1 << idx\n",
    "        \n",
    "        def dfs2(state, i, j):\n",
    "            nonlocal ans\n",
    "            idx = i * n + j\n",
    "            state |= 1 << idx\n",
    "            if state == full:\n",
    "                if (i, j) == end:\n",
    "                    ans += 1\n",
    "                return \n",
    "            for dd in [[-1, 0], [1, 0], [0, 1], [0,-1]]:\n",
    "                x, y = i + dd[0], j + dd[1]\n",
    "                idx = x * n + y\n",
    "                if x < 0 or x >= m or y < 0 or y >= n or (x, y) in block or state & (1 << idx) != 0:\n",
    "                    continue\n",
    "                dfs(state, x, y)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state, i, j):\n",
    "            res = 0\n",
    "            idx = i * n + j\n",
    "            state |= 1 << idx\n",
    "            if state == full:\n",
    "                return 1 if (i, j) == end else 0\n",
    "            for dd in [[-1, 0], [1, 0], [0, 1], [0,-1]]:\n",
    "                x, y = i + dd[0], j + dd[1]\n",
    "                idx = x * n + y\n",
    "                if x < 0 or x >= m or y < 0 or y >= n or (x, y) in block or state & (1 << idx) != 0:\n",
    "                    continue\n",
    "                res += dfs(state, x, y)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, start[0], start[1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        startx = starty = endx = endy = empty = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    empty |= (1 << (i * n + j))\n",
    "                    if grid[i][j] == 1:\n",
    "                        startx, starty = i, j\n",
    "                    elif grid[i][j] == 2:\n",
    "                        endx, endy = i, j\n",
    "        \n",
    "        @functools.cache\n",
    "        def dp(i, j, visited):\n",
    "            if i == endx and j == endy:\n",
    "                return int(visited == empty)\n",
    "            res = 0\n",
    "            for ii, jj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= ii < m and 0 <= jj < n and (visited >> (ii * n + jj)) & 1 == 0:\n",
    "                    res += dp(ii, jj, visited | (1 << (ii * n + jj)))\n",
    "            return res\n",
    "        return dp(startx, starty, 1 << (startx * n + starty))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        ds = ((-1, 0), (0, 1), (1, 0), (0, -1))\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        s = None\n",
    "        e = None\n",
    "        bs = 0\n",
    "        for r in range(h):\n",
    "            for c in range(w):\n",
    "                if grid[r][c] == 1:\n",
    "                    s = (r, c)\n",
    "                elif grid[r][c] == 2:\n",
    "                    e = (r, c)\n",
    "                    grid[r][c] = 0\n",
    "                    bs += 1\n",
    "                elif grid[r][c] == 0:\n",
    "                    bs += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(r, c, st, cnt):\n",
    "            if r == e[0] and c == e[1] and cnt == bs:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "            for dr, dc in ds:\n",
    "                rr = dr + r\n",
    "                cc = dc + c\n",
    "                if 0 <= rr < h and 0 <= cc < w and grid[rr][cc] == 0 and not st[rr * w + cc]:\n",
    "                    lst = list(st)\n",
    "                    lst[rr * w + cc] = True\n",
    "                    ans += dp(rr, cc, tuple(lst), cnt + 1)\n",
    "            return ans\n",
    "\n",
    "        dpa = dp(s[0], s[1], tuple([False] * (h * w)), 0)\n",
    "\n",
    "        dp.cache_clear()\n",
    "        return dpa\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        sr, sc = 0, 0\n",
    "        tr, tc = 0, 0\n",
    "        for r in range(n):\n",
    "            for c in range(m):\n",
    "                if grid[r][c] != -1:\n",
    "                    cnt += 1\n",
    "                if grid[r][c] == 1:\n",
    "                    sr, sc = r, c\n",
    "                elif grid[r][c] == 2:\n",
    "                    tr, tc = r, c\n",
    "        \n",
    "        @cache\n",
    "        def dfs(r: int, c: int, mask: int) -> int:\n",
    "            if r == tr and c == tc and mask.bit_count() == cnt:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for nr, nc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):\n",
    "                if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != -1 and not (mask >> (nr * m + nc) & 1):\n",
    "                    ans += dfs(nr, nc, mask | (1 << (nr * m + nc)))\n",
    "            return ans\n",
    "        return dfs(sr, sc, 1 << (sr * m + sc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsIII(self, grid: List[List[int]]) -> int:\n",
    "        allow, forbid = [], []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    start = [i, j]\n",
    "                elif grid[i][j] == 2:\n",
    "                    end = [i, j]\n",
    "                    allow.append([i, j])\n",
    "                elif grid[i][j] == 0:\n",
    "                    allow.append([i, j])\n",
    "                elif grid[i][j] == -1:\n",
    "                    forbid.append([i, j])\n",
    "        ans = [[start]]\n",
    "        while True:\n",
    "            flag = False\n",
    "            temp = []\n",
    "            count = 0\n",
    "            for x in ans:\n",
    "                xend0, xend1 = x[-1]\n",
    "                if x[-1] == end:\n",
    "                    temp.append(x)\n",
    "                    flag = True\n",
    "                    count += 1\n",
    "                else:\n",
    "                    if [xend0 + 1, xend1] in allow and [xend0 + 1, xend1] not in x:\n",
    "                        tt = x + [[xend0 + 1, xend1]]\n",
    "                        temp.append(tt)\n",
    "                        flag = True\n",
    "                    if [xend0 - 1, xend1] in allow and [xend0 - 1, xend1] not in x:\n",
    "                        tt = x + [[xend0 - 1, xend1]]\n",
    "                        temp.append(tt)\n",
    "                        flag = True\n",
    "\n",
    "                    if [xend0, xend1 + 1] in allow and [xend0, xend1 + 1] not in x:\n",
    "                        tt = x + [[xend0, xend1 + 1]]\n",
    "                        temp.append(tt)\n",
    "                        flag = True\n",
    "\n",
    "                    if [xend0, xend1 - 1] in allow and [xend0, xend1 - 1] not in x:\n",
    "                        tt = x + [[xend0, xend1 - 1]]\n",
    "                        temp.append(tt)\n",
    "                        flag = True\n",
    "\n",
    "            ans = temp\n",
    "            if count == len(ans):\n",
    "                result = copy.deepcopy(ans)\n",
    "                break\n",
    "            if flag:\n",
    "                result = copy.deepcopy(ans)\n",
    "            if not flag:\n",
    "                break\n",
    "        res = [x for x in result if len(x) == len(allow) + 1]\n",
    "        return len(res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
